package com.hyb.algorithm.data.struct.sort;

/**
 * @Author: huyanbing
 * @Date: 2021/9/13 4:24 下午
 */
public class BubbleSort {





    /**
     * 希尔排序
     * 希尔排序 跟 选择排序的区别是
     * <p>
     * 希尔排序
     * 希尔排序是插入排序的进化版本，插入排序是每一次轮询是跟前一个元素比较，而希尔排序是每次轮询跟前第h个元素比较
     *
     * @param arr
     */
    public static void shellSort(Comparable[] arr) {

        int step = 3;
        int n = arr.length;
        int h = 0;

        while (step * h < n) {
            h = step * h + 1;
        }

        while (h > 0) {

            for (int i = h; i < n; i++) {
                //对 arr[i],arr[i-h] arr[i-2*h]  arr[i-3*h]  使用插入排序
                for (int j = i; j >= h; j -= h) {
                    if (arr[j - h].compareTo(arr[j]) > 0) {
                        SortTestHelper.swap(arr, j - h, j);
                    }
                }
            }
            h = h / step;
        }
    }

    /**
     * @param arr
     */
    public static void insertSort(Comparable[] arr) {

        //选择排序是每次都从i前往后比较
        //插入排序是每次都是  从i 向前比较
        for (int i = 1; i < arr.length; i++) {
            for (int j = i; j >= 0; j--) {
                if (arr[j - 1].compareTo(arr[j]) > 0) {
                    SortTestHelper.swap(arr, j - 1, j);
                }
            }
        }
    }


    /**
     * 选择排序  O n^2
     *
     * @param arr
     */
    public static void selectSort(Comparable[] arr) {

        //每次交换 [i,n) 最小的元素
        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j - 1].compareTo(arr[j]) < 0) {
                    minIndex = j - 1;
                }
            }

            if (i == minIndex) {
                continue;
            }

            SortTestHelper.swap(arr, minIndex, i);
        }

    }

    /**
     * 冒泡排序
     *
     * @param arr
     */
    public static void bubbleSort(Comparable[] arr) {

        int end = arr.length;
        int last = 0;

        for (int i = 0; i < arr.length; i++) {
            for (int j = 1; j < end; j++) {
                if (arr[j - 1].compareTo(arr[j]) > 0) {
                    SortTestHelper.swap(arr, j - 1, j);
                    //记录最后一次交换的位置，在此之后的元素在下一轮扫描中均不考虑
                    last = j;
                }
            }

            if (last > 0) {
                end = last;
            }
        }
    }
}
